#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode *sortedArrayToBST(vector<int> &num);
TreeNode *BuildSubTree(vector<int>::const_iterator begin, 
    vector<int>::const_iterator end);

int main()
{

    return 0;
}

TreeNode *sortedArrayToBST(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() functionT
    return BuildSubTree(num.begin(), num.end());

}

TreeNode *BuildSubTree(vector<int>::const_iterator begin, 
                       vector<int>::const_iterator end){
    if(begin == end)
        return NULL;
    vector<int>::const_iterator mid = begin + (end - begin)/2;
    TreeNode *pRoot = new TreeNode(*mid);
    //left
    if(begin != mid){
        pRoot->left = BuildSubTree(begin, mid);
    }
    //right
    if(mid+1 != end){
        pRoot->right = BuildSubTree(mid+1, end);
    }
    return pRoot;

}